import fileinput
import operator

def createStructure():
    dic={}
    accuracy_dic={}
    count=0
    average=0
    recommendations=0
    n=0
    for line in fileinput.input(['D:/python/DATSET/3daysdata/D/train.csv']):
            try:
                n=n+1
                print "n   ", n
                if n<=1100000:
                    train(line,dic,accuracy_dic)
                else:
                    print count
                    value,recommendations = findRecommnedationList(dic,line,count, average,recommendations,accuracy_dic)
                    average = value[0]
                    count=value[1]
#                else:
#                    break
            except:
                continue
    print "Average : ",average
    print "Count : ",count
    print "recommendations : ",recommendations
    print "Coverage ", calCoverage(count, recommendations)

def calCoverage(count, recommendations):
    return float(count)*100/float(recommendations)    

def train(line, dic, accuracy_dic):
    line= line.strip().rstrip(',')
    line=line.split(',')
    length=len(line)-1
    if dic.has_key(length):
        dic_tree=dic.get(length)
        dic_tree.add(line)
    else:
        tree=HybridTree()
        tree.add(line)
        dic[length]=tree
        accuracy_dic[length]=0
 
def findRecommnedationList(dic,line,count,average,recommendations,accuracy_dic):
    line= line.strip().rstrip(',')
    sessionlist=line.split(',')
    templist=[]   
    sessionsize=len(sessionlist)
#    print "sessionlist   ",sessionlist
#    print 1
#    print "Line ",sessionlist
    
    for e in range(0,sessionsize):
#        print "e   ",e
        list2=[]
        recommendationlist=[]
        recommendationdic={}
#        print 2
        if not e==(sessionsize-1):
            templist.append(sessionlist[e])
#            print "Temp list ",templist
#            print "templist   ",templist
            recommendations+=1
            for r in reversed(templist):
#                print 3
                list2.append(r)
                list4=list2
#                print "list2   ",list2
                list4.reverse()
                length=len(list2)
#                print "length   ",length
#                print "List 4   ",list4
                if dic.has_key(length):
                    dic_tree=dic.get(length)
                    list3 = dic_tree.checkPath(list4)                   
                    if list3:
                        list3.sort(key=lambda x: x._count, reverse=True)
#                        print 3
                        if len(list3)>1:
#                            recommendationlist.append(list3[0:20])
                            recommendationdic[length]=list3[0:1]
#                            print recommendationdic[length]
                        else:
#                            recommendationlist.append(list3[0:])
                            recommendationdic[length]=list3[0:]
#            recommendationdic1=eliminateDuplicate(recommendationdic)
            dictionary=recommenddomiansdic(recommendationdic,accuracy_dic)
            if dictionary.__len__():
                count+=1
                list8=[]
                list9=sorted(dictionary.items(), key=lambda x: x[1], reverse=True)
                for i in list9:
                    list8.append(i[0])
                if len(list8)>20:
                    value=evaluate1(list8[0:20], recommendationdic,accuracy_dic, sessionlist[e+1], count, average)
                else:
                    value=evaluate1(list8[0:], recommendationdic,accuracy_dic, sessionlist[e+1], count, average)
#                print 11
#                list9=sorted(dictionary.items(), key=lambda x: x[1], reverse=True)
#                print "List 9", list9
#                print "Lit 9 length ", len(list9)
#                print "actual   ", sessionlist[e+1]
#                list9.sort(key=operator.attrgetter("_count"),reverse=false)
#                list9.sort(key=lambda x: x._count)
#                if len(list9)>20:
#                    value=evaluate(list9[0:20], sessionlist[e+1], count, average)
#                else:
#                    value=evaluate(list9[0:], sessionlist[e+1], count, average)                    
    train(line,dic,value[3])
#    print 12
    return value,recommendations

def evaluate1(recommendationlist,recommendationdic, accuracy_dic,actual,count,average):
    correct=0
#    print "Evaluate recommend list ",recommendationlist
#    print "Actual ",actual
#    print "Count ",count
#    print "Average ",average
    node =HybridNode(None,actual)
    length =len(recommendationlist)
    if actual in recommendationlist:
        average = calculateAccuracy(1,average,count)
        for key,value in recommendationdic.iteritems():
            if node in value:
                accuracy_dic[key]=calculateAccuracy(1,accuracy_dic[key],count)
            else:
                accuracy_dic[key]=calculateAccuracy(0,accuracy_dic[key],count)   
        return (average,count,correct,accuracy_dic)
    else:
        average=calculateAccuracy(0,average,count)
        accuracy_dic=decreaseAccuracy(accuracy_dic,count) 
        return (average,count,correct,accuracy_dic)      

def decreaseAccuracy(accuracy_dic,count):
    for key,value in accuracy_dic.iteritems():
        accuracy_dic[key]=calculateAccuracy(0,accuracy_dic[key],count)  
    return accuracy_dic

def calculateAccuracy(correct,average,count):
        return ((int(count)-1)*float(average)+int(correct))/int(count)
    
def recommenddomiansdic(recommendationdic,accuracydic):
    domaindic={}
    for key,value in recommendationdic.iteritems():
        for j in value:
            if not domaindic.has_key(j._item):
                domaindic[j._item]=calculateWeight1(key, accuracydic,j._count)
#                print "Weight ", domaindic[j._item]
            else:
                domaindic[j._item]+=calculateWeight1(key, accuracydic,j._count)
#                print "Weight ", calculateWeight(key, accuracydic)
    return domaindic

#def eliminateDuplicate(recommendationdic): 
#    for key,i in recommendationdic.iteritems():
#        if i:
#            recommendationdic[key]=list(set(i))
#    return recommendationdic 
def calculateWeight1(key, accuracydic,count):
#    print "*"
#    print "% ",accuracydic.items()
#    totAccuracy=0
#    for i,j in accuracydic.iteritems():
#        totAccuracy+=float(j)*count
#    t=0
#    if not totAccuracy==0:
#        t=float(accuracydic[key])/totAccuracy
    t=count*float(accuracydic[key])
    return t

def calculateWeight(key, accuracydic):
#    print "*"
#    print "% ",accuracydic.items()
    totAccuracy=0
    for i,j in accuracydic.iteritems():
        totAccuracy+=float(j)
    t=0
    if not totAccuracy==0:
        t=float(accuracydic[key])/totAccuracy
    return t
    
def recommenddomians(sessionlist):
    dic={}
    for i in sessionlist:
        if i:
            for j in i:
                if dic.has_key(j._item):
                    count = dic.get(j._item)+j._count
                    dic[j._item]=count
                else:
                    dic[j._item]=j._count
    return dic            
    
def test(dic):
    print dic.values()
    for s,r in dic.items():
        print "Length ",s
        r.printTree(r._root)
#    tree.printTree(tree._root)
        
class HybridTree(object):
    def __init__(self):
        self._root = HybridNode(self, -1, None)

    @property
    def root(self):
        return self._root

    def add(self, transaction):
        point = self._root

        for item in transaction:
            next_point = point.search(item)
            if next_point:
                next_point.increment()
            else:
                next_point = HybridNode(self, item)
                point.add(next_point)
            point = next_point

    def printTree(self, root1):
        print "Root ", root1._item
        print root1._children.values()
        for x in root1._children.values():
            self.printTree(x)
#        for child in root1._children:
#            self.printTree(child)
#        for child in self.root1.children():
#            print child.item()
#            self.printTree(child)
            
    def checkPath(self,sessionlist):
        sessionlist.reverse()
        point = self._root
        for i in sessionlist:
            node = point.search(i)
            if node:
                point=node
            else:
                return None
        return point._children.values()
               

class HybridNode(object):
    def __init__(self, tree, item, count=1):
        self._tree = tree
        self._item = item
        self._parent = None
        self._children = {}
        self._neighbor = None
        self._count = count

    def add(self, child):
        if not isinstance(child, HybridNode):
            raise TypeError("Can only add other Node as children")

        if not child.item in self._children:
            self._children[child.item] = child
            child.parent = self

    def search(self, item):
        try:
            return self._children[item]
        except KeyError:
            return None
        
    def __eq__(self, other):
        return self._item==other._item
    
    def __hash__(self):
        return hash(self._item)

#    def remove(self, child):
#        try:
#            if self._children[child.item] is child:
#                del self._children[child.item]
#                child.parent = None
#                self._tree._removed(child)
#                for sub_child in child.children:
#                    try:
#                        # Merger case: we already have a child for that item, so
#                        # add the sub-child's count to our child's count.
#                        self._children[sub_child.item]._count += sub_child.count
#                        sub_child.parent = None # it's an orphan now
#                    except KeyError:
#                        # Turns out we don't actually have a child, so just add
#                        # the sub-child as our own child.
#                        self.add(sub_child)
#                child._children = {}
#            else:
#                raise ValueError("that node is not a child of this node")
#        except KeyError:
#            raise ValueError("that node is not a child of this node")

    def __contains__(self, item):
        return item in self._children

    @property
    def tree(self):
        """The tree in which this node appears."""
        return self._tree

    @property
    def item(self):
        """The item contained in this node."""
        return self._item

    @property
    def count(self):
        """The count associated with this node's item."""
        return self._count

    def increment(self):
        """Increments the count associated with this node's item."""
        if self._count is None:
            raise ValueError("Root nodes have no associated count.")
        self._count += 1

    @property
    def root(self):
        """True if this node is the root of a tree; false if otherwise."""
        return self._item is None and self._count is None

    @property
    def leaf(self):
        """True if this node is a leaf in the tree; false if otherwise."""
        return len(self._children) == 0

#    def parent(self):
#        doc = "The node's parent."
#        def fget(self):
#            return self._parent
#        def fset(self, value):
#            if value is not None and not isinstance(value, HybridNode):
#                raise TypeError("A node must have an HybridNode as a parent.")
#            if value and value.tree is not self.tree:
#                raise ValueError("Cannot have a parent from another tree.")
#            self._parent = value
#        return locals()
#    parent = property(**parent())


    @property
    def children(self):
        """The nodes that are children of this node."""
#        print self._children.items()
#        return 1
        return tuple(self._children.itervalues())
#        return list(self._children.itervalues())

    def inspect(self, depth=0):
        print ('  ' * depth) + repr(self)
        for child in self.children:
            child.inspect(depth + 1)

    def __repr__(self):
        if self.root:
            return "<%s (root)>" % type(self).__name__
        return "<%s %r (%r)>" % (type(self).__name__, self.item, self.count)

    
if __name__ == "__main__": createStructure()